typedef struct bstn {
    int var;
    int count;
    struct bstn *left;
    struct bstn *right;
}bstnode;

#include <time.h>
#include <stdlib.h>

void bst_insert(bstnode **root, bstnode *bnode) {
    bstnode *rnodep = *root;
    if(rnodep)
        if(rnodep->var == bnode->var)
            rnodep->count++;
        else if(rnodep->var > bnode->var)
            bst_insert(&rnodep->left, bnode);
        else 
            bst_insert(&rnodep->right, bnode);
    else
        *root = bnode;
}

bstnode *auto_gen_bst(bstnode *root, int n) {
    int i;
    bstnode *tmpnodep;
    srand(time(NULL));
    for(i=0; i<n; i++) {
        tmpnodep = malloc(sizeof(bstnode));
        tmpnodep->var = rand()%1024;
        tmpnodep->count = 1;
        tmpnodep->left = tmpnodep->right = NULL;
        bst_insert(&root, tmpnodep);
    }
    return root;
}

#include <stdio.h>
void pre_order_traversal(bstnode *root) {
    if(root) {
        pre_order_traversal(root->left);
        printf("node_var: %d, count: %d\n", root->var, root->count);
        pre_order_traversal(root->right);
    }
}

void in_order_traversal(bstnode *root) {
    if(root) {
        printf("node_var: %d, count: %d\n", root->var, root->count);
        pre_order_traversal(root->left);
        pre_order_traversal(root->right);
    }
}

void post_order_traversal(bstnode *root) {
    if(root) {
        pre_order_traversal(root->right);
        printf("node_var: %d, count: %d\n", root->var, root->count);
        pre_order_traversal(root->left);
    }
}


int main(void) 
{
    bstnode *root = auto_gen_bst(NULL, 20);
    printf("pre_order_traversal:\n");
    pre_order_traversal(root);
    printf("in_order_traversal:\n");
    in_order_traversal(root);
    printf("post_order_traversal:\n");
    post_order_traversal(root);
}

